package tree;

import java.util.Comparator;

public class RBTree<E> extends BBST<E> {
	private static final boolean RED = false;
	private static final boolean BLACK = true;

	public RBTree() {
		this(null);
	}

	public RBTree(Comparator<E> comparator) {
		super(comparator);

	}

	@Override
	protected Node<E> createNode(E element, Node<E> parent) {
		return new RBNode<>(element, parent);
	}

	@Override
	protected void afterAdd(Node<E> node) {
		Node<E> parent = node.parent;
		if (parent == null) {
			black(node);
			return;
		}

		if (isBlack(parent)) {
			return;
		}

		Node<E> grand = red(parent.parent);
		Node<E> uncle = parent.sibling();
		if (isRed(uncle)) {
			black(parent);
			black(uncle);
			afterAdd(grand);
			return;
		}

		if (parent.isLeftChild()) {
			if (node.isLeftChild()) {// LL
				black(parent);
			} else {// LR
				black(node);
				rotateLeft(parent);
			}
			rotateRight(grand);
		} else {
			if (node.isLeftChild()) {// RL
				black(node);
				rotateRight(parent);
			} else {// RR
				black(parent);
			}
			rotateLeft(grand);
		}

	}

	@Override
	protected void afterRemove(Node<E> node, Node<E> replacement) {
		if (isRed(node)) {// 删除的是红色节点
			return;
		}
		if (isRed(replacement)) {// 替换的是红色节点，删除的就是黑色节点(不会有俩红色连续)，删除就是把下面节点的值给上面，然后删除下面的，
			black(replacement);
			return;
		}
		if (node.parent == null) {
			return;
		}

		// 删除的是黑色叶子结点
		// node就是被删除的节点，此刻已经删除了，如果replacement存在，这时候replacement就是当前的节点，已经替换完了
		//
		Node<E> parent = node.parent;
		boolean left = parent.left == null || node.isLeftChild();// 左边为空，被删除的在左边，是左节点
		Node<E> sibling = left ? parent.right : parent.left;

		if (!left) { // 被删除的节点是右节点
			if (isRed(sibling)) {// 兄弟节点是红色 // 先旋转一次
				black(sibling);
				red(parent);
				rotateRight(parent);
				sibling = parent.right;
			}
			if (isBlack(sibling.left) && isBlack(sibling.right)) { // 兄弟节点没法借，下溢合并
				boolean parentBlack = isBlack(parent);// 判断父节点的颜色，如果是红色的，红色的父节点下来和子节点合并也能保证这棵树上的黑色节点数量没有失衡
				black(parent);// 替换后，父节点染黑，子节点染红，（父节点为什么要染黑？？？？）因为如果向下后，父节点成为了根节点，必须是黑的！还有如果他是根节点，他的另一边还有个你的兄弟节点，兄弟节点不为黑的话失衡
				red(sibling);// 合并后兄弟节点染红，不然又不平衡了
				if (parentBlack) {
					afterRemove(parent, null);
				}
			} else {
				if (isRed(sibling.right)) {// 兄弟节点的右节点存在并且肯定是红！
					rotateLeft(sibling);
					sibling = parent.left;
				}
				color(sibling, colorOf(parent));
				black(sibling.left);
				black(parent);
				rotateRight(sibling);
			}
		} else {
			if (isRed(sibling)) {// 兄弟节点是红色 // 先旋转一次
				black(sibling);
				red(parent);
				rotateLeft(parent);
				sibling = parent.left;
			}
			if (isBlack(sibling.left) && isBlack(sibling.right)) { // 兄弟节点没法借，下溢合并
				boolean parentBlack = isBlack(parent);// 判断父节点的颜色，如果是红色的，红色的父节点下来和子节点合并也能保证这棵树上的黑色节点数量没有失衡
				black(parent);// 替换后，父节点染黑，子节点染红，（父节点为什么要染黑？？？？）因为如果像下后，父节点成为了根节点，必须是黑的！还有如果他是根节点，他的另一边还有个你的兄弟节点，兄弟节点不为黑的话失衡
				red(sibling);// 合并后兄弟节点染红，不然又不平衡了
				if (parentBlack) {
					afterRemove(parent, null);
				}
			} else {
				if (isRed(sibling.left)) {// 兄弟节点的右节点存在并且肯定是红！
					rotateRight(sibling);
					sibling = parent.right;
				}
				color(sibling, colorOf(parent));
				black(sibling.right);
				black(parent);
				rotateRight(sibling);
			}
		}

	}

	private Node<E> red(Node<E> node) {
		return color(node, RED);
	}

	private Node<E> black(Node<E> node) {
		return color(node, BLACK);
	}

	private boolean colorOf(Node<E> node) {
		if (node == null) {
			return BLACK;
		}
		return ((RBNode<E>) node).color;
	}

	private boolean isBlack(Node<E> node) {
		return colorOf(node) == BLACK;
	}

	private boolean isRed(Node<E> node) {
		return colorOf(node) == RED;
	}

	private Node<E> color(Node<E> node, boolean color) {
		if (node == null) {
			return null;
		}
		((RBNode<E>) node).color = color;
		return node;
	}

	private static class RBNode<E> extends Node<E> {
		boolean color = RED;

		public RBNode(E element, Node<E> parent) {
			super(element, parent);
		}

		@Override
		public String toString() {
			String parentString = "";
			if (parent != null) {
				parentString = parent.element.toString();
			}
			String yanseString = !color ? "红" : "黑";
			return element + "_" + parentString + "_" + yanseString + "____";

		}
	}

}
